package com.programmercarl.tree;

import java.util.HashMap;

/**
 * https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/?envType=problem-list-v2&envId=8VDkRxcG
 *
 * @author yulongtian
 * @create 2024-12-23 14:48
 */
public class Test15 {
    public static void main(String[] args) {
        Test15 test15 = new Test15();
        TreeNode treeNode = test15.buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});
        System.out.println(treeNode.val);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    HashMap<Integer, Integer> num_index_map;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        num_index_map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            num_index_map.put(inorder[i], i);
        }

        return preorderTraversal(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    public TreeNode preorderTraversal(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        // 终止条件 左闭右开
        if (inStart >= inEnd || postStart >= postEnd) {
            return null;
        }

        // 找到根节点 创建本节点
        int rootVal = postorder[postEnd - 1];
        TreeNode treeNode = new TreeNode(rootVal);
        int inRootIndex = num_index_map.get(rootVal);
        int leftLen = inRootIndex - inStart;


        // 左节点
        treeNode.left = preorderTraversal(inorder, inStart, inRootIndex, postorder, postStart, postStart + leftLen);

        // 右节点
        treeNode.right = preorderTraversal(inorder, inRootIndex + 1, inEnd, postorder, postStart + leftLen, postEnd - 1);


        // 返回本节点
        return treeNode;
    }

}

